package main

func isValid(board [][]byte, x int, y int) bool {
	// |
	for _, row := range board {
		if row[x] == 'Q' {
			return false
		}
	}
	// \
	i := y - 1
	j := x - 1
	for i >= 0 && j >= 0 {
		if board[i][j] == 'Q' {
			return false
		}
		i--
		j--
	}
	// /
	i = y - 1
	j = x + 1
	for i >= 0 && j < len(board) {
		if board[i][j] == 'Q' {
			return false
		}
		i--
		j++
	}
	return true
}

var result [][]string

func backtrack(board [][]byte, y int) {
	n := len(board)
	if y == n {
		ans := make([]string, n)
		for i, row := range board {
			ans[i] = string(row)
		}
		result = append(result, ans)
		return
	}
	for i := 0; i < n; i++ {
		if !isValid(board, i, y) {
			continue
		}
		board[y][i] = 'Q'
		backtrack(board, y+1)
		board[y][i] = '.'
	}
}

func solveNQueens(n int) [][]string {
	result = make([][]string, 0)
	board := make([][]byte, n)
	for i := range board {
		row := make([]byte, n)
		for j := range row {
			row[j] = '.'
		}
		board[i] = row
	}
	backtrack(board, 0)
	return result
}
